﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;
int brokenCalc(int startValue, int target) {
	int ret = 0;
	while (target > startValue)
	{
		if (target % 2 == 1)
			target++;
		else
			target /= 2;
		ret++;
	}
	return startValue - target + ret;
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
	sort(intervals.begin(), intervals.end());
	int n = intervals.size();
	vector<vector<int>> ret;
	int left = intervals[0][0], right = intervals[0][1];
	for (int i = 1; i < n; i++)
	{
		int a = intervals[i][0], b = intervals[i][1];
		if (a <= right)
			right = max(right, b);
		else
		{
			ret.push_back({ left,right });
			left = a;
			right = b;
		}
	}
	return ret;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
	int n = intervals.size();
	int ret = 0;
	int left = intervals[0][0], right = intervals[0][1];
	for (int i = 1; i < n; i++)
	{
		int a = intervals[i][0], b = intervals[i][1];
		if (a < right)
		{
			if (right > b)
			{
				left = a;
				right = b;
			}
			ret++;
		}
	}
	return ret;
}
int findMinArrowShots(vector<vector<int>>& points) {
	sort(points.begin(), points.end());
	int n = points.size();
	int ret = 0;
	int left = points[0][0], right = points[0][1];
	for (int i = 1; i < n; i++)
	{
		int a = points[i][0], b = points[i][1];
		if (a <= right)
		{
			left = max(left, a);
			right = min(right, b);
		}
		else
		{
			ret++;
			left = a;
			right = b;
		}
	}
	return ret;
}
int integerReplacement(int n) {
	int ret = 0;
	while (n > 1)
	{
		if (n % 2 == 0)
		{
			n /= 2;
			ret++;
		}
		else if (n == 3)
		{
			n = 1;
			ret += 2;
		}
		else if ((n / 2) % 2 == 1)
		{
			n = (n + 1) / 4;
			ret += 3;
		}
		else
		{
			n = (n - 1) / 4;
			ret += 3;
		}
	}
	return ret;
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
	// 贪⼼ + ⼆分
	sort(envelopes.begin(), envelopes.end(), [&](const vector<int>&v1,const vector<int>& v2)
		{
			return v1[0] == v2[0] ? v1[1] > v2[1]:v1[0] < v2[0];
		});
	int n = envelopes.size();
	vector<int> v;
	v.push_back(envelopes[0][1]);
	for (int i = 1; i < n; i++)
	{
		int a = envelopes[i][1];
		if ( a > v.back())
			v.push_back(a);
		else
		{
			int left = 0, right = v.size() - 1;
			while (left < right)
			{
				int mid = left + (right - left) / 2;
				if (a < v[mid])
					right = mid - 1;
				else
					left = mid;
			}
			v[left] = a;
		}
	}
	return v.size();
}
int pileBox(vector<vector<int>>& box) {
	sort(box.begin(), box.end(), [&](const vector<int>& v1, const vector<int>& v2)
		{
			return v1[2] < v2[2];
		});
	int n = box.size();
	vector<int> dp(n);
	for (int i = 0; i < n; i++)
		dp[i] = box[i][2];
	int ret = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (box[i][0] > box[j][0] && box[i][1] > box[j][1])
				dp[i] = max(dp[i], dp[j] + box[i][2]);
		}
		ret = max(ret, dp[i]);
	}
	return ret;
}
int maxSumDivThree(vector<int>& nums) {
	int n = nums.size();
	vector<vector<int>> dp(3, vector<int>(n + 1));
	dp[0][0] = 0, dp[1][0] = INT_MIN, dp[2][0] = INT_MIN;
	for (int i = 1; i <= n; i++)
	{
		if (nums[i - 1] % 3 == 0)
		{
			dp[0][i] = max(dp[0][i - 1], dp[0][i - 1] + nums[i - 1]);
			dp[1][i] = max(dp[1][i - 1], dp[1][i - 1] + nums[i - 1]);
			dp[2][i] = max(dp[2][i - 1], dp[2][i - 1] + nums[i - 1]);
		}
		else if (nums[i - 1] % 3 == 1)
		{
			dp[0][i] = max(dp[0][i - 1], dp[2][i - 1] + nums[i - 1]);
			dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + nums[i - 1]);
			dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + nums[i - 1]);
		}
		else
		{
			dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + nums[i - 1]);
			dp[1][i] = max(dp[1][i - 1], dp[2][i - 1] + nums[i - 1]);
			dp[2][i] = max(dp[2][i - 1], dp[0][i - 1] + nums[i - 1]);
		}
	}
	return dp[0][n];
}
int maxSumDivThree(vector<int>& nums) {
	int x1, x2, y1, y2, sum = 0;
	x1 = x2 = y1 = y2 = 0x3f3f3f3f;
	for (auto& e : nums)
	{
		sum += e;
		if (e % 3 == 1)
		{
			if (e < x1)
			{
				x2 = x1;
				x1 = e;
			}
			else if (e < x2)
				x2 = e;
		}
		else if (e % 3 == 2)
		{
			if (e < y1)
			{
				y2 = y1;
				y1 = e;
			}
			else if (e < y2)
				y2 = e;
		}
	}
	if (sum % 3 == 0)
		return sum;
	if (sum % 3 == 1)
		return max(sum - x1, sum - y1, y2);
	else
		return max(sum - x1 - x2, sum - y1);
}
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
	int n = barcodes.size();
	vector<int> ret(n);
	unordered_map<int, int> hash;
	int maxval = 0, maxcount = 0;
	for (auto& e : barcodes)
	{
		if (maxcount < ++hash[e])
		{
			maxval = e;
			maxcount = hash[e];
		}
	}
	int index = 0;
	for (int i = 0; i < maxcount; i++)
	{
		ret[index] = maxval;
		index += 2;
	}
	hash.erase(maxval);
	for (auto& e : hash)
	{
		for (int i = 0; i < e.second; i++)
		{
			if (index >= n)
				index = 1;
			ret[index] = e.first;
			index += 2;
		}
	}
	return ret;
}
string reorganizeString(string s) {
	int hash[26] = { 0 };
	char maxval;
	int maxcount = 0;
	for (auto& e : s)
	{
		if (maxcount < ++hash[e - 'a'])
		{
			maxval = e;
			maxcount = hash[e - 'a'];
		}
	}
	int n = s.size();
	if (maxcount > (n + 1) / 2)
		return "";
	string ret;
	ret.resize(n);
	int index = 0;
	for (int i = 0; i < maxcount; i++)
	{
		ret[index] = maxval;
		index += 2;
	}
	hash[maxval - 'a'] = 0;
	for (int i = 0; i < 26; i++)
	{
		for (int j = 0; j < hash[i]; j++)
		{
			if (index >= n)
				index = 1;
			ret[index] = 'a' + i;
			index += 2;
		}
	}
	return ret;
}
int main()
{

	return 0;
}